10285. Гимнастика для коров

Чтобы привести себя в хорошую физическую форму, коровы решили заняться гимнастикой! Фермер Джон поручает своей любимой корове Бесси тренировать  других коров и оценивать их прогресс по мере освоения различных гимнастических навыков.

На каждом из  тренировочных занятий Бесси составляет рейтинг из  коров в соответствии с их результатами. После этого ей становится интересно, насколько стабильны эти рейтинги. Пара разных коров считается стабильной, если одна корова неизменно показывала лучший результат, чем другая, на каждом занятии.

Помогите Бесси вычислить общее количество стабильных пар.

Вход. Первая строка содержит два положительных целых числа k (1 ≤ k ≤ 10)  и n (1 ≤ n ≤ 20). Каждая из следующих k строк содержит целые числа от 1 до n в некотором порядке, задающие рейтинг коров (коровы обозначаются числами 1 … n). Если A стоит перед B в одной из таких строк, это означает, что корова A показала результат лучше, чем корова B.

Выход. Выведите количество стабильных пар.

Пример входа	Пример выхода
3 4 4 1 2 3 4 1 3 2 4 2 1 3	4

РЕШЕНИЕ

перебор

Анализ алгоритма

Для решения задачи достаточно перебрать все пары коров. Для каждой пары необходимо пройти по всем тренировкам и проверить, что их относительный порядок в рейтингах не меняется ни на одной тренировке.

Реализация алгоритма

Объявим массив data, который хранит рейтинги коров на тренировках:

· data[i][j] содержит номер коровы, занявшей место j на i-ой тренировке.

int data[10][20];

Функция better возвращает, стоит ли корова a раньше коровы b в s-й тренировке.

bool better(int a, int b, int s)

{

int apos, bpos;

for (int i = 0; i < n; i++)

{

В переменных apos и bpos находим соответственно позиции коровы a и коровы b в s-й тренировке.

if (data[s][i] == a) apos = i;

if (data[s][i] == b) bpos = i;

}

Сравниваем позиции коров.

return apos < bpos;

}

Функция pair вычисляет, на скольких тренировках корова a лучше (стоит раньше в рейтинге), чем корова b.

int pair(int a, int b)

{

Количество искомых тренировок подсчитываем в переменной cnt.

int cnt = 0;

В переменной s перебираем номера тренировок.

for (int s = 0; s < k; s++)

Если корова a лучше коровы b на тренировке s, то увеличиваем cnt на 1.

if (better(a, b, s)) cnt++;

return cnt;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &k, &n);

for (i = 0; i < k; i++)

for (j = 0; j < n; j++)

scanf("%d", &data[i][j]);

В переменной res подсчитываем общее количество стабильных пар коров.

res = 0;

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

Пара (i, j) будет стабильной, только если корова i будет лучше коровы j на каждой из k тренировок.

if (pair(i, j) == k) res++;

Выводим ответ.

printf("%d\n", res);